\documentclass[a4paper,10pt]{article}

%linguagem
\usepackage[brazil]{babel}
%encodificação
\usepackage[utf8]{inputenc}
%biblioteca de matemática
\usepackage{amssymb,amsmath}
%pacote para codigo fonte
\usepackage{listings}
%figuras
\usepackage{graphicx}
%cores
\usepackage{color}
%paragrafo no inicio da secao
\usepackage{indentfirst}
%url
\usepackage{framed, url}
\usepackage{fancyvrb}

%define a cor "claro"
\definecolor{claro}{gray}{0.96}

%configurações do listings
\lstset{frame=trBL, numbers=left, xleftmargin=0pt, xrightmargin=0pt,
breaklines=true, language=Java, backgroundcolor=\color{claro}}

\begin{document}

\input{./titulo.tex}
\tableofcontents
\pagebreak

\section{Introdução}
O compilador é o programa responsável por transformar um código-fonte de uma
linguagem de programação em outra linguagem, geralmente um código binário, ou
executável. O processo de compilação é feito através de várias etapas, como
mostrado na figura \ref{fig:fases}. 

\begin{figure}[h] 
\centering
\includegraphics[scale=0.6]{imagens/fases.png} 
\label{fig:fases} 
\caption{Fases do processo de compilação} 
\end{figure}

Depois da geração de código pelo compilador, um interpretador é usado para
executar as instruções contidas neste código e finalmente realizar as tarefas
descritas no código-fonte feito pelo programador.

\begin{figure}[h]
\centering
\includegraphics[scale=0.4]{imagens/interpretador.png}
\label{fig:interpretador}
\caption{Interpretador}
\end{figure}


O objetivo deste trabalho é implementar um interpretador para a máquina virtual
Bós. Dentre as funções do interpretador, estão:
\begin{itemize}
\item Ler a entrada.
\item Gerar uma memória de instruções.
\item Executar corretamente cada instrução, utilizando uma pilha e um
``display''.
\item Apresentar o estado do interpretador.
\item Gerar uma saída.
\end{itemize}

 
\section{Desenvolvimento}

O interpretador possui vários componentes, que auxiliam na execução das
instruções. A figura \ref{fig:mepa} mostra a arquitetura do mesmo:

\begin{figure}[h]
\centering
\includegraphics[scale=0.4]{imagens/mepa.png}
\label{fig:mepa}
\caption{Arquitetura do interpretador}
\end{figure}

\begin{Verbatim}[frame=single]

private final static int D_LENGTH = 100;
private final static int M_LENGTH = 50;

private int[] display = new int[D_LENGTH];
private int sp;
private int[] pilha = new int[M_LENGTH];
private MemInst meminst;
private int pc;

\end{Verbatim}

\clearpage
\subsection{Display}

O ``display'' é usado para fazer os elos de acesso entre funções aninhadas. Ele
é implementado como um arranjo de inteiros, de tamanho ``D\_LENGTH''.

\begin{figure}[h]
\centering
\includegraphics[scale=0.4]{imagens/display.png}
\label{fig:display}
\caption{Display}
\end{figure}

\begin{Verbatim}[frame=single]
private final static int D_LENGTH = 100;
private int[] display = new int[D_LENGTH];
\end{Verbatim}

\subsection{Pilha}

A pilha é usada para armazenar os dados necessários para a execução do programa,
como endereços de retorno, variáveis, valores temporários e resultados de
operações. A variável ``sp'' aponta sempre para o topo da pilha, e serve como
referência para as operações de empilhamento e desempilhamento. A pilha também
consiste de um arranjo de inteiros de tamanho ``M\_LENGTH''.

\begin{figure}[h]
\centering
\includegraphics[scale=0.4]{imagens/pilha.png}
\label{fig:pilha}
\caption{Pilha}
\end{figure}

\begin{Verbatim}[frame=single]
private final static int M_LENGTH = 50;
private int sp;
private int[] pilha = new int[M_LENGTH];
\end{Verbatim}

\clearpage
\subsection{Programa}

As instruções contidas no código-fonte são armazenadas na memória de instruções.
Ela consiste de um vetor contendo as instruções, na ordem em que aparecem no
código, e uma tabela contendo os ``labels'', que são marcadores de endereços
usados pelo programador.

\begin{figure}[h]
\centering
\includegraphics[scale=0.4]{imagens/meminst.png}
\label{fig:meminst}
\caption{Memória de instruções}
\end{figure}

\begin{Verbatim}[frame=single]
private final static int I_LENGTH = 100;
private final static int L_LENGTH = 100;

private Instrucao[] instrucoes = new Instrucao[I_LENGTH];
private Label[] labels = new Label[L_LENGTH];
\end{Verbatim}

\subsubsection{Instruções}

Cada instrução possui um nome, um identificador numérico e um arranjo contendo
os argumentos que esta instrução recebeu.

\begin{figure}[h]
\centering
\includegraphics[scale=0.4]{imagens/instrucao.png}
\label{fig:instrucao}
\caption{Instrução}
\end{figure}

\begin{Verbatim}[frame=single]
private String nome_;
private int id_;
private int[] args_ = new int[NARGS];

private final static int NARGS = 3;
\end{Verbatim}

\clearpage
\subsubsection{Label}

Um ``label'' define uma posição no código-fonte. Ele contém o nome e a posição
do mesmo.

\begin{figure}[h]
\centering
\includegraphics[scale=0.4]{imagens/label.png}
\label{fig:label}
\caption{Label}
\end{figure}

\begin{Verbatim}[frame=single]
private class Label{
	private String label_;
	private int posicao_;

	public Label(String s, int p){
		this.label_ = s;
		this.posicao_ = p;
	}
}
\end{Verbatim}

\section{Instruções para utilização}

Para utilizar o interpretador deve ser executa o programa Teste.class e enviar
como parâmetro o modo de execução e o nome do arquivo de entrada.

Os modos de execução podem ser:
\begin{itemize}
\item normal - Gera a saída padrão do programa.
\item dumpPilha - Imprime um ``dump'' da pilha ao final do programa.
\item dumpDisplay - Imprime um ``dump'' do display ao final do programa.
\item dumpAll - Imprime um ``dump'' da pilha e do display ao final do programa.
\end{itemize}

Um exemplo de comando:

\medskip
\colorbox{claro}{\$ java Teste dumpPilha in.txt}
\medskip

O arquivo de entrada deve conter apenas a sequencia instruções a serem
interpretadas.

\clearpage
\section{Testes}

\subsection{Teste 1}

O primeiro teste recebe 3 inteiros de entrada e não imprime nada na saída.

\begin{Verbatim}[frame=single]

********* SAIDA *********

Digite um inteiro:
3
Digite um inteiro:
4
Digite um inteiro:
5

********* DUMP DA PILHA *********

SP = 3
Pilha 0: -29
Pilha 1: 3
Pilha 2: 4
Pilha 3: 5
Pilha 4: -29
Pilha 5: 32
Pilha 6: 8
Pilha 7: 5
Pilha 8: 0
Pilha 9: 0

********* DUMP DO DISPLAY *********

Display 0: 0
Display 1: 0
Display 2: 0
Display 3: 0
Display 4: 0
Display 5: 0
Display 6: 0
Display 7: 0
Display 8: 0
Display 9: 0

\end{Verbatim}

\subsection{Teste 2}

O segundo teste recebe dois números inteiros e imprime na saída.

\begin{Verbatim}[frame=single]

********* SAIDA *********

Digite um inteiro:
19
Digite um inteiro:
87
43
87

********* DUMP DA PILHA *********

SP = 4
Pilha 0: 19
Pilha 1: 1
Pilha 2: 43
Pilha 3: 87
Pilha 4: 2
Pilha 5: 87
Pilha 6: 0
Pilha 7: 0
Pilha 8: 0
Pilha 9: 0

********* DUMP DO DISPLAY *********

Display 0: 0
Display 1: 0
Display 2: 0
Display 3: 0
Display 4: 0
Display 5: 0
Display 6: 0
Display 7: 0
Display 8: 0
Display 9: 0


\end{Verbatim}

\subsection{Teste 3}

O terceiro teste recebe dois inteiros e imprime na saída.

\begin{Verbatim}[frame=single]

********* SAIDA *********

Digite um inteiro:
23
Digite um inteiro:
17
1

********* DUMP DA PILHA *********

SP = 5
Pilha 0: 1
Pilha 1: 17
Pilha 2: 23
Pilha 3: 1
Pilha 4: 1
Pilha 5: 0
Pilha 6: 1
Pilha 7: 1
Pilha 8: 1
Pilha 9: 0

********* DUMP DO DISPLAY *********

Display 0: 0
Display 1: 0
Display 2: 0
Display 3: 0
Display 4: 0
Display 5: 0
Display 6: 0
Display 7: 0
Display 8: 0
Display 9: 0

\end{Verbatim}

\subsection{Teste 4}

Apenas imprime 4 inteiros na saída.

\begin{Verbatim}[frame=single]

********* SAIDA *********

5
16
7
41

********* DUMP DA PILHA *********

SP = 2
Pilha 0: 41
Pilha 1: 8
Pilha 2: 16
Pilha 3: 7
Pilha 4: 29
Pilha 5: 0
Pilha 6: 33
Pilha 7: 0
Pilha 8: 0
Pilha 9: 0

********* DUMP DO DISPLAY *********

Display 0: 0
Display 1: 10
Display 2: 0
Display 3: 0
Display 4: 0
Display 5: 0
Display 6: 0
Display 7: 0
Display 8: 0
Display 9: 0

\end{Verbatim}

\subsection{Teste 5}

Imprime dois inteiros na saída.

\begin{Verbatim}[frame=single]

********* SAIDA *********

0
100

********* DUMP DA PILHA *********

SP = -1
Pilha 0: 0
Pilha 1: 27
Pilha 2: 0
Pilha 3: 0
Pilha 4: 35
Pilha 5: 0
Pilha 6: 0
Pilha 7: 0
Pilha 8: 0
Pilha 9: 25

********* DUMP DO DISPLAY *********

Display 0: 0
Display 1: 8
Display 2: 21
Display 3: 0
Display 4: 0
Display 5: 0
Display 6: 0
Display 7: 0
Display 8: 0
Display 9: 0

\end{Verbatim}

\subsection{Teste 6}

Imprime um inteiro na saída.

\begin{Verbatim}[frame=single]

********* SAIDA *********

30

********* DUMP DA PILHA *********

SP = 0
Pilha 0: 30
Pilha 1: 30
Pilha 2: 6
Pilha 3: 0
Pilha 4: 0
Pilha 5: 0
Pilha 6: 0
Pilha 7: 28
Pilha 8: 6
Pilha 9: 1

********* DUMP DO DISPLAY *********

Display 0: 0
Display 1: 6
Display 2: 11
Display 3: 16
Display 4: 36
Display 5: 0
Display 6: 0
Display 7: 0
Display 8: 0
Display 9: 0

\end{Verbatim}

\section{Conclusão}
		
O desenvolvimento deste trabalho possibilitou o aprendizado acerca do
funcionamento de um interpretador. A implementação foi facilitada pela grande
quantidade de código e algoritmos prontos que puderam ser reaproveitados, como
as funções do ``MEPA''. O programa foi desenvolvido de forma modular, para
favorecer o uso do mesmo nas outras etapas da construção de um compilador.

\section{Código-fonte}

\subsection{Teste.java}

\lstinputlisting[xleftmargin=-80px,xrightmargin=-80px]{../src/Teste.java}

\subsection{Instrucao.java}

\lstinputlisting[xleftmargin=-80px,xrightmargin=-80px]{../lib/Instrucao.java}

\subsection{MemInst.java}

\lstinputlisting[xleftmargin=-80px,xrightmargin=-80px]{../lib/MemInst.java}

\subsection{MEPA.java}

\lstinputlisting[xleftmargin=-80px,xrightmargin=-80px]{../lib/MEPA.java}

\clearpage
\begin{thebibliography}{99}
\bibitem{wiki} \url{http://en.wikipedia.org/wiki/Interpreter_(computing)}
\bibitem{mepa} \url{https://homepages.dcc.ufmg.br/~mariza/Cursos/CompiladoresI/2010-1/Pagina/Trabalho/Mepa/InterpretadorMEPA/especificacaoCodigoMEPA-p4.pdf}
\bibitem{livro} Alfred V. Aho, Ravi Sethi and Jeffrey D. Ullman, \emph{Compilers - Principles Techniques and Tools}, 2006
\end{thebibliography}

\end{document}
